/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 16
 * Time: 15:56
 */
//牛客 不同路径的数目(一)
public class Solution4 {
    public int uniquePaths (int m, int n) {
        //dp[i][j]表示走到第i行第j列时有多少种走法
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;//填dp表时，要保证多加出来的行和列(为防止越界而虚拟出来的格子)里面的值不会影响后面填表的正确性
        for (int i = 1; i <= m ; i++) {
            for (int j = 1; j <= n ; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];//起点到dp[i-1][j]的走法种数和dp[i-1][j]到dp[i][j]的走法种数是相同的，因为dp[i-1][j]到dp[i][j]是一步而不是一种走法。所以dp[i-1][j]表示从dp[i][j]上面走到dp[i][j]有多少种走法，dp[i][j - 1]表示从dp[i][j]左边面走到dp[i][j]有多少种走法
            }                                          //两者相加即走到dp[i][j]有多少种走法
        }
        return dp[m][n];
    }
}
